#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#include <vector>
#include <string>


//904. 水果成篮
class Solution {
public:
    int totalFruit(vector<int>& fruits)
    {
        int hash[100010] = { 0 };//记得初始化，局部变量没有初始化默认是随机值
        int left = 0, right = 0, count = 0, n = fruits.size(), len = 0;
        while (right < n)
        {
            //1. 进窗口
            if (hash[fruits[right]] == 0) count++;
            hash[fruits[right]]++;

            //2. 判断
            while (left < n && count > 2)
            {
                hash[fruits[left]]--;//3. 出窗口
                if (hash[fruits[left]] == 0) count--;
                left++;
            }

            //4. 更新结果
            len = max(len, right - left + 1);
            //5. 窗口移动
            right++;
        }
        return len;
    }
};



//438. 找到字符串中所有字母异位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> ret;
        int hash[128] = { 0 };
        for (int i = 0; i < p.size(); i++)
        {
            hash[p[i]]--;
        }

        int left = 0, right = 0, n = s.size(), count = 0, n2 = p.size();
        while (right < n)
        {
            //1. 进窗口
            hash[s[right]]++;
            count++;

            //2. 判断
            while (left < n && hash[s[right]] > 0)
            {
                hash[s[left++]]--;// 3.出窗口
                count--;
            }

            //4. 更新值
            if (count == n2) ret.push_back(left);

            //5. 移动窗口
            right++;
        }
        return ret;
    }
};


//30. 串联所有单词的子串
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        vector<int> ret;
        int len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++)
        {
            unordered_map<string, int> hash;
            for (auto& s : words) hash[s]--;
            for (int left = i, right = i, count = 0; right + len <= s.size(); right += len)
            {
                //1. 进窗口
                string in = s.substr(right, len);
                hash[in]++;
                count++;
                //判断
                while (hash[in] > 0)
                {
                    //3. 出窗口
                    string out = s.substr(left, len);
                    hash[out]--;
                    count--;
                    left += len;
                }
                //4. 更新结果
                if (count == m) ret.push_back(left);
            }
        }
        return ret;
    }
};


//76. 最小覆盖子串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        int hash1[128] = {0};//统计t中每个字符出现的频率
        int kinds = 0;//用于统计t中的种类
        for (auto tmp : t) 
            if (hash1[tmp]++ == 0) kinds++;

        int hash2[128] = {0};//统计s中每个字符出现的频率
        int min =  INT_MAX, begin = -1, n = s.size();
        for (int left = 0, right = 0, count = 0; right < n; right++)
        {
            //进窗口 + 维护 count
            char in = s[right];
            if (++hash2[in] == hash1[in]) count++; //进窗口 + 维护count

            while (count == kinds)
            {
                //更新结果
                if (min > right - left + 1)
                {
                    min = right - left + 1;
                    begin = left;
                }
                //出窗口
                char out = s[left++];
                if (hash2[out]-- == hash1[out]) count--;// 出窗口+ 维护 count
            }
        }
        if (begin == -1) return "";
        else return s.substr(begin, min);
    }
};